package from_0_to_50;

public class Q044_isMatch {

    public static void main(String[] args) {
        String s = "";
        String p = "******";
//        String s = "aab";
//        String p = "c*a*b";
        boolean isMatch = new Q044_isMatch().isMatch(s, p);
        boolean isMatch3 = new Q044_isMatch().isMatch3(s, p);
        System.out.println("ismatch = " + isMatch);
        System.out.println("ismatch = " + isMatch3);
    }

    /**
     * 动态规划的方式
     * '?' 可以匹配任何单个字符。
     * '*' 可以匹配任意字符串（包括空字符串）。
     * s 可能为空，且只包含从 a-z 的小写字母。
     * p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
     */

    public boolean isMatch(String s, String p) {
        int sLen = s.length();  // 列
        int pLen = p.length();  // 行
        boolean[][] dp = new boolean[p.length()+1][s.length()+1];
        dp[0][0] = true;   // 1 表示匹配
        for (int i = 1; i <= p.length(); i++) {
            if(s.length() == 0 && p.charAt(i-1) == '*'){
                dp[i][0] = dp[i-1][0] == true ? true :false;
            }else {
                for (int j = 1; j <= s.length(); j++) {
                    if(p.charAt(i-1) == '*'){
                        dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j];
                        dp[i][0] = dp[i-1][0] == true ? true :false;
                    }
                    if(p.charAt(i-1) == '?' || p.charAt(i - 1) == s.charAt(j - 1)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        Show_dp(s.toCharArray(),p.toCharArray(),dp);
        return dp[pLen][sLen];
    }
    public boolean isMatch3(String s, String p) {
        int sLen = s.length();  // 列
        int pLen = p.length();  // 行
        boolean[][] dp = new boolean[2][s.length()+1];
        dp[0][0] = true;   // 1 表示匹配
        for (int i = 1; i <= p.length(); i++) {
            int i1 = i % 2;
            int i2 = i1 == 0 ? 1 : 0;
            if(s.length() == 0 && p.charAt(i-1) == '*'){
                    dp[i1][0] = dp[i1][0] == true ? true :false;
            }else {
                for (int j = 1; j <= s.length(); j++) {
                    if (p.charAt(i - 1) == '*') {
                        dp[i1][j] = dp[i1][j - 1] || dp[i2][j - 1] || dp[i2][j];
                        dp[i1][0] = dp[i2][0] == true ? true : false;
                    }
                    if (p.charAt(i - 1) == '?' || p.charAt(i - 1) == s.charAt(j)) {
                        dp[i1][j] = dp[i2][j - 1];
                    }
                }
            }
        }
        return dp[pLen%2][sLen];
    }
    public static void Show_dp(char[] sChars, char[] pChars, boolean[][] dp){
        System.out.print("\t\t\t");
        for (int i = 0; i < sChars.length; i++) {
            System.out.print(sChars[i]+"\t\t");
        }
        System.out.println();
        for (int i = 0; i <= pChars.length; i++) {
            if(i != 0)
                System.out.print(pChars[i-1]+"\t");
            else
                System.out.print("\t");

            for (int j = 0; j <= sChars.length; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println();
    }

}
